package com.test;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//双指针法实现
public class 三数之和 {

    public List<List<Integer>> threeSum(int[] nums) {
        //数组排序
        Arrays.sort(nums);
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        for (int i=0;i<nums.length;i++){
            //数组中所有的元素大于0
            if (nums[i]>0){
                break;
            }
            if (i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int lp=i+1;
            int rp=nums.length-1;

            while (lp<rp){
                //求和
                int sum=nums[i]+nums[lp]+nums[rp];
                if (sum==0){
                    List<Integer> integers = Arrays.asList(nums[i], nums[lp], nums[rp]);
                    result.add(integers);
                    lp++;
                    rp--;
                    //这里 lp 和rp是分别++和——过的值了
                    while (lp<rp && nums[rp]==nums[rp+1]){
                        rp--;
                    }
                    while (lp<rp && nums[lp]==nums[lp-1]){
                        lp++;
                    }
                }else if (sum<0){
                    lp++;
                }else {
                    rp--;
                }
            }
        }
        return result;

    }
}
